package com.darrenchan.leetcode;

import java.util.*;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-26 20:18
 */
public class Q653 {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }

        Stack<TreeNode> stack = new Stack<>();
        Set<Integer> set = new HashSet<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.add(root);
                root = root.left;
            } else {
                root = stack.pop();
                if (!set.contains(root.val)) {
                    set.add(k - root.val);
                } else {
                    return true;
                }
                root = root.right;
            }
        }

        return false;
    }
}
